/**
 * 给定二维数组，每个格子为左右括号之一
 * 问从左上到右下是否存在括号匹配的路径
 * 规划模板就是0和1，存在就是1，不存在就是0
 * 此时注意到到目前为止的状态与左括号的剩余数量有关 
 * 设 Dijk是从起点到ij位置且左括号剩余k个，是否存在的记录
 * 则  当Aij是左括号时, Dijk = D[i-1][j][k-1] | D[i][j-1][k-1]
 *     当Aij是右括号时，Dijk = D[i-1][j][k+1] | D[i][j-1][k+1]
 */
class Solution {

using vi = vector<int>;
using vvi = vector<vi>;

int N, M;
vector<vvi> D;

public:
    bool hasValidPath(vector<vector<char>>& grid) {
        N = grid.size();
        M = grid[0].size();
        D.assign(N, vvi(M, vi(N + M, 0)));
        if(')' == grid[0][0]) return false;

        D[0][0][1] = 1;
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(0 == i and 0 == j) continue;

            auto & d = D[i][j];
            int v = '(' == grid[i][j] ? 1 : -1;
            if(i > 0){
                const auto & pre = D[i - 1][j];
                for(int k=0;k<d.size();++k){
                    if(pre[k] and 0 <= k + v and k + v < d.size()){
                        d[k + v] = 1;
                    } 
                }
            }
            if(j > 0){
                const auto & pre = D[i][j - 1];
                for(int k=0;k<d.size();++k){
                    if(pre[k] and 0 <= k + v and k + v < d.size()){
                        d[k + v] = 1;
                    } 
                }                
            }
        }
        return D[N - 1][M - 1][0];
    }
};